Volume rendering is an important branch of computer graphics, following behind the development of geometric rendering and pixel rendering. Volume rendering refers to the direct rendering of a volume data set, also referred to as a "volume," to show the characteristics of the interior of a solid object when displayed on a 2D graphics device. A volume data set is a three-dimensional array of voxels. These voxels typically are organized on a regular gridded lattice. Voxels have been defined as sample points separated by a finite distance. Each voxel has a position and a value. The voxel position is a three-tuple specifying an x, y, and z position within the 3D voxel array. The voxel value depends upon its format. For example, a voxel may have an intensity element and an index element. These elements are usually treated differently in the volume rendering process. The collection of values for all points in the volume is called a scalar field of the volume.
Volume data sets can be generated by numerous means, but most commonly by some method of 3D scanning or sampling and by numerical modeling. For example, a volume data set may be generated by Magnetic Resonance Imaging, or MRI, wherein the density of human or animal tissue is computed at each point of a 3D grid. A display of this information could indicate the boundaries of the various types of tissue, as indicated by density changes. Volume rendering is the process of displaying this data on a 2D graphics device.
The coordinate system of the volume is referred to as the source space. The very first voxel in a volume data set in source space has coordinates (x.sub.o,y.sub.o,z.sub.o) wherein x.sub.o, y.sub.o, and z.sub.o represent the lowermost value of all x, y, and z positions in the volume data set, and is considered to be the origin of the volume data set. Normally the coordinates for this origin voxel are set to (0,0,0). The three coordinates, in order, correspond to the column, row, and slice of the image in the volume data set. The very last voxel in a volume data set is located on the opposite diagonal corner from the origin source voxel of the volume data set. Its coordinates are designated as (x.sub.u,y.sub.u,z.sub.u) wherein x.sub.u, y.sub.u, and z.sub.u, represent the uppermost values of all x, y, and z positions in the volume data set.
Volume data sets can be quite large and thus can place a strain on computer system resources. For example, a typical volume data set from a MRI scanner may contain 6.7 million voxels or more, whereas polygon data sets for geometric rendering typically contain less than 1/2 million polygons. Thus, there is a much greater need for special purpose hardware acceleration when rendering volumes.
In volume rendering there is often a need to be able to view the rendered image from various projections. The coordinate system of the viewer is referred to as view space or image space. It describes from which direction the volume data set is viewed and rendered. Thus, a key step in the volume rendering process is the 3D spatial volume transformation of the original volume data set from source space to view space. Typical types of transformations required may include zoom, pan, rotation, and even shear of the input volume for projection into an output raster type display device. Once a transformation has been done, various resampling techniques must be applied, such as nearest neighbor or trilinear interpolation, in addition to other steps in the volume rendering pipeline, to determine pixel values for rendering.
A ray is an imaginary line emanating from a pixel on an image plane that passes through the volume. On this ray discrete steps are taken and at each step sample points along the ray are interpolated. Sample points along the ray from the image plane to the volume do not contribute to the rendered image, as well as sample points along the ray after the ray exits the volume. Depending on the view desired by the user, some rays may not pass through the volume at all and thus contribute nothing to the rendered image. Conventional volume rendering implementations typically process all sample points along a ray whether the ray passes through the volume or not or whether the sample points along the ray are within the volume or not. Although possible with software only, to decrease rendering time these implementations often require special hardware solutions to check and keep track of where sample points fall. Thus, much time and system resources are wasted in the rendering process in checking and keeping track of sample points that are not needed for rendering the image. This slows down greatly the rendering process and requires costly expenditures for hardware.
There is a need in the art for an improved method of volume rendering that can eliminate the processing of rays that do not contribute to the final rendered image. There is also a need in the art for a method that does not require hardware solutions and can thus save costly VLSI space. There is a further need in the art for a volume rendering method that only processes the sample points on a ray that actually pass through the volume data set and contribute to the final rendered image. It is thus apparent that there is a need in the art for an improved method of volume rendering which solves the objects of the invention. The present invention meets these needs.
This application is related to application Ser. No. 08/866,859 filed May 30, 1997 entitled Fixed-Point Method for Fast and Precise 3D Spatial Transformations of Shaz Naqvi, Barthold Lichtenbelt, and Russell Huonder, and application Ser. No. 08/865,756 filed May 30, 1997 entitled Ray Transform Method for a Fast Perspective View Volume Rendering of Shaz Naqvi, Russell Huonder, and Barthold Lichtenbelt, which are incorporated herein by reference for all that is disclosed and taught therein.